package chart.mst;

import chart.图的存储.AbstractGraph;
import chart.图的存储.AdjacencyMatrix;
import chart.图的存储.AdjacencyTable;
import chart.图的存储.Edge;

import java.util.Arrays;
import java.util.List;

/**
 * 普里姆算法
 * <p>针对顶点</p>
 * <p>贪心</p>
 * <p>适用于稠密图</p>
 * <p>生成树（极小连通子图）不唯一, 但最小权值都是一样的</p>
 * <p>算法要点：</p>
 * <p>isJoin 数组：顶点是否加已经加入到生成树中</p>
 * <p>lowCost: 将顶点加入到生成树的最小代价</p>
 *
 * <p>时间复杂度：O(V ^ V)</p>
 *
 * @author yezh
 * @date 2023/7/10 15:23
 */
public class Prime {

    public static void main(String[] args) {
        AbstractGraph graph = new AdjacencyMatrix(4, false);
        Edge e1 = new Edge(0, 1, 2);
        Edge e2 = new Edge(0, 2, 1);
        Edge e3 = new Edge(1, 2, 4);
        Edge e4 = new Edge(1, 3, 2);
        Edge e5 = new Edge(2, 3, 1);
        List<Edge> edges = Arrays.asList(e1, e2, e3, e4, e5);
        graph.createGraph(edges);
        System.out.println("total: " + prime(graph));

        graph = new AdjacencyTable(4, false);
        graph.createGraph(edges);
        System.out.println("total: " + prime(graph));
    }

    public static int prime(AbstractGraph graph) {
        int ans = 0;
        int v = graph.getV();
        boolean[] isJoin = new boolean[v];
        int[] lowCost = new int[v];
        Arrays.fill(lowCost, Integer.MAX_VALUE);
        lowCost[0] = 0;
        List<Edge> neighborEdge = graph.getNeighborEdge(0);
        if (neighborEdge == null) return -1;
        for (int k = 0; k < v; k++) {
            int vertex = -1, cost = Integer.MAX_VALUE;
            // 找到没有加入到生成树的最小 lowCost
            for (int i = 0; i < v; i++)
                if (!isJoin[i] && lowCost[i] < cost) {
                    vertex = i;
                    cost = lowCost[i];
                }
            System.out.print(vertex + " ");
            if (vertex == -1) return -1;
            isJoin[vertex] = true;
            ans += cost;
            for (Edge edge : graph.getNeighborEdge(vertex))
                if (!isJoin[edge.getArcHead()] && lowCost[edge.getArcHead()] > edge.getWeigh())
                    lowCost[edge.getArcHead()] = edge.getWeigh();
        }
        return ans;
    }

}
